public class LeetCode1711 {

    public static void main(String[] args) {
        int[] deliciousness = {1, 3, 5, 7, 9};

        System.out.println(countPairs(deliciousness));
    }

    public static int countPairs(int[] deliciousness) {
        // 获取deliciousness中的极大值与极小值
        int min = deliciousness[0];
        int max = deliciousness[0];
        for (int delicious : deliciousness) {
            if (delicious < min) {
                min = delicious;
            }
            if (delicious > max) {
                max = delicious;
            }
        }
        // 不使用HashMap去重而是使用数组存储（天知道为什么内存没有超限）
        int[] map = new int[max - min + 1];
        long res = 0;
        for (int delicious : deliciousness) {
            // s 用于描述 2 的幂次，每次循环都 * 2
            for (int i = 1; ; i <<= 1) {
                int x = i - delicious;
                // 对应的补数小于数组中最小的数
                if (x < min) {
                    continue;
                }
                // 对应的补数大于数组中最大的数
                if (x > max) {
                    break;
                }
                // 给结果加上补数出现的次数
                res += map[x - min];
            }
            // 添加当前数进数组
            map[delicious - min]++;
        }
        return (int) res;
    }
}
